The applications and uses of bar codes and matrix codes are well known and increasing. Bar codes and matrix codes are forms of "dataforms", which for purposes of the invention are defined to include all arrangements whereby data is fixed in some form of machine readable copy. Thus, dataforms include one and two dimensional bar codes, matrix codes and graphic codes, as well as words and numbers and other symbols, which may be printed or etched on any suitable medium. Dataforms are utilized to encode information which may be recovered for further use in a variety of manners. For example, a printed bar code may be optically scanned to derive reflectance values which are digitized, stored in buffer memory and subsequently decoded to recover the data encoded in the bar code.
Regardless of the particular type of dataform, an image is typically acquired and stored as pixel values for further processing. An image of a bar code or other dataform existing as a graphic image can be acquired by use of a CCD scanner, laser scanner, sensor array or other suitable arrangement which is capable of distinguishing between different levels of illumination reflected from the dataform. In a bar code for example, the graphic image generally comprises cells of contrasting reflectivity (e.g., black bar type elements printed on a white background, with white spaces between the bars). In the stored image the pixel values thus represent illumination level changes of reflected light ("light" being defined as encompassing the entire electromagnetic spectrum for present purposes). The illumination level changes may typically be stored as pixel values in an image buffer memory or other storage medium in bit map or other form which, while representative of pixel values for an image, may utilize any appropriate data storage format.
For dataform readers, the resolution capability, and thereby the cost of the scanning device or other sensor, as well as the data storage medium, are directly dependent upon the resolution required in the overall decoding process. On a basic level, the resolution characterizing both the pixel data image acquisition and storage must be adequate to permit detection of the position of the smallest image element of interest in the dataform. For present purposes, the bars or other elements utilized in encoding of a dataform are termed "cells" and the smallest image element of interest is termed a "module". The narrowest cell or bar of a bar code will thus be one module wide. If, for example, the width of a module is many times larger than the size of a pixel within the acquired pixel image, it will be appreciated that such module width will be represented by many pixels and its position will be correspondingly easy to detect. Thus, the resolution, which may be measured in pixels-per-module, will be related to the minimum cell width. Conversely, it should be also recognized that if a module dimension is smaller than the size of one pixel in the pixel data image, it will not be possible to detect cell positions with accuracy adequate to enable reliable recovery of data encoded in the dataform. As the size of the smallest image element or cell of interest can be very small within complex dataforms such as 2D bar codes and matrix codes, there is a need to detect the precise location of cell edge transitions with accuracy adequate to enable reliable recovery of all data encoded in the dataform. At the same time, there is a conflicting need to avoid the cost, size and power requirements of higher resolution imaging devices, storage devices, etc.
In the present state of the art, there typically is a requirement that the width of a cell must be no smaller than the dimension represented by two side-by-side pixels in the pixel image. This is another way of expressing a current state of the art standard for bar code decoding, which holds that detecting of a bar code or other dataform requires, at minimum, at least two pixels-per-cell along one axis. This state of the art minimum requirement is further discussed and illustrated in application Ser. No. 08/245,613 filed May 19, 1995, and commonly assigned herewith. FIG. 1A, shows bar code cells and the pixels size relationship for a few pixels within an overall image. The individual pixels may be in any lateral positioning relationship with the bar code cells, and the provision of at least two pixels-per-cell enables determination of the relative cell positions adequately for decoding. For the two-dimensional case (as for cells of a matrix code dataform, wherein both lateral and vertical positioning of square cells are employed for encoding data) detecting typically requires, on a consistent basis, a resolution of at least two pixels-per-cell along two perpendicular axes, which equates to four pixels-per-cell, as illustrated in FIG. 1B. To achieve the desired decoding resolution, the storage or memory medium must have at least the same resolution capability of storing at least two pixels-per-cell for one axis and four pixels-per-cell for the 2D case. These standards, together with the overall size and the image cell content of a complete dataform to be decoded, determine the overall size, resolution and cost of the sensor unit and storage medium necessary to acquire and store the pixel data image. As a result, as dataforms increase in complexity even larger sensor and storage capacity is required. There is thus a need for reliable methods of locating dataform cell edges which are usable with image resolutions better than two pixels-per-cell along one axis in the dataform. Such methods can save both sensor and storage cost and capacity.
An important consideration is the effect of noise on achievable resolution in reading and decoding dataforms. As is known, spurious effects relating to printing or surface variations in a dataform, or to lens, sensor or other optical variations, as well as to electrical signal variations, typically introduce variations in recorded gray scale values. As a practical matter, in the presence of noise each gray scale value may be distorted by being changed to a higher or lower value. If image data stored in memory for a particular dataform were known to include noise variations to a specific maximum magnitude, spurious results could be excluded by ignoring all gray scale value variations smaller than a noise threshold or margin determined in view of such specific maximum magnitude. However, the stored image data may also include valid dataform information represented by small gray scale value differentials. By setting a noise margin adequate to avoid effects of the noise, valid dataform information would, therefore, be lost with the noise. Such loss of dataform information will be reflected as a loss of resolution, limiting the processing of fine detail in dataform reading and decoding. There is thus a need for improved dataform operation to increase achievable resolution in the presence of noise.
Existing edge detection methods available for use in dataform readers rely upon a variety of approaches to locate the edge transitions of cells within the dataform. Commonly used methods employ fixed threshold, residual (original signal minus a low-pass filtered version of the signal) or other algorithms such as Laplacian or Gaussian algorithms to locate the signal transitions. The fixed threshold technique is limited in detection of edges when the contrast of narrow bar code patterns is reduced by convolution and sampling effects introduced during image capture. Other algorithms are similarly not efficient when implemented digitally and may be limited to the at least two pixels-per-cell resolution requirement along an axis. The other techniques in general require filtering operations which in turn require excessive multiplication or other processing operations. There may also be limitations as to the permissible range of cell width variations, due in part to the use of a fixed set of filter parameters which can not readily be changed. The result is to limit one or more of achievable resolution, efficiency of operation and flexibility of performance of available dataform decoders.
In view of the foregoing, objects of the present invention are to provide improved methods of locating dataform cell edge transitions which are characterized by one or more of the following capabilities:
higher resolution performance in the presence of noise; PA1 improved sub-pixel resolution for location of dataform cell edge transitions with reduced imaging and storage resolution requirements; PA1 selective application of a noise margin to image data represented within different gray scale ranges; PA1 automatic determination of a noise margin; PA1 automatic selection of sub-pixel image processing on an as-required basis; and PA1 use of whole-pixel image processing when sub-pixel processing is not required for dataform decoding.